package william.backtracing;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/4/3
 * @description <a href="https://leetcode.cn/problems/permutations/description/">...</a>
 */
public class Leetcode46_全排列 {
    /**
     * 保存最终结果
     */
    private List<List<Integer>> result = new ArrayList<>();

    /**
     * 记录数字状态:当前数字是否被使用过
     */
    private boolean[] used;

    /**
     * 采用递归+回溯算法
     * 采用数组used记录每个数字是否被使用过
     * 在递归过程中,将每个未使用过的数字添加到排列的末尾,并继续进行递归处理
     * 递归调用结束后进行回溯,将该数字的使用状态清空,并从排列中移除当前数字
     * <p>
     * 时间复杂度O(N*N!)
     * 空间复杂度O(N) 额外申请一个used数组,数组长度为数字数量
     */
    public List<List<Integer>> permute(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return Collections.emptyList();
        }

        //初始化状态
        used = new boolean[nums.length];

        //调用递归实现
        backTracing(nums, 0, new LinkedList<>());

        //返回结果
        return result;
    }

    /**
     * 递归+回溯实现
     * 对数组nums[idx]位置的元素进行全排列,排列结果追加到prefix中
     */
    private void backTracing(int[] nums, int idx, LinkedList<Integer> prefix) {
        //递归终止条件:已经生成一个全排列,保存到结果中
        if (idx == nums.length) {
            result.add(new ArrayList<>(prefix));
            return;
        }

        //针对数组中的每一个未使用过的元素,递归进行全排列
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }

            //在全排列中追加当前元素
            prefix.addLast(nums[i]);
            //将当前元素标记为已使用
            used[i] = true;

            //递归调用
            backTracing(nums, idx + 1, prefix);

            //状态回溯
            used[i] = false;
            prefix.removeLast();
        }
    }
}
